/*
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，
使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。摘自百度百科

对所有的未标记的点依次dfs搜索，进入dfs方法的顺序即dfs访问顺序，
离开dfs的顺序(即离开递归栈的顺序)即拓扑排序。
书上说当且仅当一幅有向图是无环图时它才能进行拓扑排序。
有环判断的代码已经写过了，而且就算有环此api也不会出现bug，所以这里不考虑了。
千万注意：如果有环，那么这个环的点之间可能混进这些点可达的点，例如0,1,2组成了环，
有[0,3]这条边，那么可能生成[0,1,3,2]这样的的顺序。这个在强连通性里有相关描述。
*/
function DepthFirstOrder(V,G){
    for(let i=0;i<V;i++){
        if(!marked[i]){dfs(i,G)}
    }
}

function dfs(v,G){
    marked[v]=true
    visitList.push(v)
    for(let j in G[v]){
        let w=G[v][j]
        if(!marked[w]){dfs(w,G)}
    }
    topoList.unshift(v)
}




//let generateDirectedGraph=require("./graph").generateDirectedGraph


let V=10
var edges=[]
for(let i=0;i<V;i++){
    let x=Math.floor(Math.random()*V)
    let y=Math.floor(Math.random()*V)
    edges.push([x,y])
}


console.log(G=generateDirectedGraph(V,edges,false))
var marked=[]
for(let i=0;i<V;i++){
    marked[i]=false
}
var visitList=[]
var topoList=[]
DepthFirstOrder(V,G)
console.log('visitList-->',visitList)
console.log('topoList-->',topoList)
